#include <cstdio>
#define mod 1000000007

int prime[ 5000 ], primec, fac[ 50 ][ 2 ], fn;
bool visit[ 31623 ];

void getprime( )
{
    int i, j;
    for ( i = 2; i < 31623; i++ )
        if ( !visit[ i ] )
        {
            prime[ primec++ ] = i;
            for ( j = i * 2; j < 31623; j += i )
                visit[ j ] = 1;
        }
}

long long euler( long long n )
{
    long long ret = n;
    int i;
    for ( i = 0; i < fn; i++ )
        if ( n % fac[ i ][ 0 ] == 0 )
            ret = ret / fac[ i ][ 0 ] * ( fac[ i ][ 0 ] - 1 );
    return ret % mod;
}

long long a, c, ans;

long long pow( long long a, long long n )
{
    long long p = 1, ret = 1;
    while ( p <= n ) p <<= 1;
    p >>= 1;
    while ( p )
    {
        ret = ret * ret % mod;
        if ( p & n ) ret = ret * a % mod;
        p >>= 1;
    }
    return ret;
}

long long extgcd( long long a, long long b, long long &x, long long &y )
{
    if ( b == 0 ) { x = 1; y = 0; return a; }
    long long d = extgcd( b, a % b, x, y );
    long long t = x; x = y; y = t - a / b * y;
    return d;
}

void dfs2( int p, long long i, long long k, long long d, long long &ret )
{
    int j;
    if ( i != k )
    {
        ret = ( ret + euler( i ) * pow( d, k ) ) % mod;
        ret = ( ret + euler( k ) * pow( d, i ) ) % mod;
    }
    else
        ret = ( ret + euler( i ) * pow( d, i ) ) % mod;
    for ( j = p; j < fn; j++ )
        if ( k % fac[ j ][ 0 ] == 0 && k / fac[ j ][ 0 ] >= i * fac[ j ][ 0 ] )
            dfs2( j, i * fac[ j ][ 0 ], k / fac[ j ][ 0 ], d, ret );
}

long long calc( long long b, long long k )
{
    long long d, ret = 0, x, y;
    long long i;
//    printf("%I64d %I64d\n", b, k);
    d = ( pow( c, b ) + 2 * pow( c, ( b + 3 ) / 4 ) + pow( c, ( b + 1 ) / 2 ) ) % mod;
    d = d * 250000002 % mod;
    dfs2( 0, 1, k, d, ret );
    extgcd( k, mod, x, y );
    x = ( x + mod ) % mod;
    ret = ret * x % mod;
    return ret * c % mod;
}

void dfs( long long b, long long a, int p )
{
    int i;
    ans = ( ans + calc( b, a ) ) % mod;
    for ( i = p; i < fn; i++ )
        if ( fac[ i ][ 1 ] >= 2 )
        {
            fac[ i ][ 1 ] -= 2;
            dfs( b * fac[ i ][ 0 ] * fac[ i ][ 0 ], a / fac[ i ][ 0 ] / fac[ i ][ 0 ], i );
            fac[ i ][ 1 ] += 2;
        }
}

void getfac( long long a )
{
    int i;
    for ( i = 0; i < fn; i++ )
        while ( a % fac[ i ][ 0 ] == 0 )
        {
            a /= fac[ i ][ 0 ];
            fac[ i ][ 1 ]++;
        }
    for ( i = 0; i < primec && prime[ i ] * prime[ i ] <= a; i++ )
        if ( a % prime[ i ] == 0 )
        {
            fac[ fn ][ 0 ] = prime[ i ];
            fac[ fn ][ 1 ] = 0;
            while ( a % prime[ i ] == 0 )
            {
                fac[ fn ][ 1 ]++;
                a /= prime[ i ];
            }
            fn++;
        }
    if ( a > 1 )
    {
        fac[ fn ][ 0 ] = a;
        fac[ fn++ ][ 1 ] = 1;
    }
}

int main( )
{
    int i, t, cas = 1;
    getprime( );
    scanf("%d", &t);
    while ( t-- )
    {
        scanf("%I64d%I64d", &a, &c);
        if ( a == 1 )
        {
            printf("Case %d: %I64d\n", cas++, c);
            continue;
        }
        fn = 0;
        getfac( a - 1 );
        getfac( a + 1 );
        a = a * a - 1;
        ans = 0;
        dfs( 1, a, 0 );
        printf("Case %d: %I64d\n", cas++, ans);
    }
    return 0;
}
